The present invention relates to a computer memory cache and, more particularly, to determining a single reference residency time for data within the cache.
Caching is a technique used to improve computer performance at all levels of the computer storage hierarchy. When a central processing unit (CPU) requests data for processing, the data is often moved from a slower, less costly memory to a high speed, more costly, memory that can be accessed directly by the CPU. The higher speed memory is generically referred to as a cache. In some data processing systems, the cache is housed within a cache control unit (CCU).
A typical caching algorithm permits data staged to the cache to remain in the cache for some indeterminate interval of time. If the CPU re-references the data while the data is still in the cache, then the caching algorithm allows the data to continue to remain in the cache. On the other hand, the caching algorithm will xe2x80x9cage outxe2x80x9d old data and overwrite the old data with new data if the old data is not timely re-referenced by the CPU.
Most cache management systems are based on a least recently used (LRU) algorithm. The LRU algorithm uses a stack of a limited size. A most recently used data request is placed on the top of the stack. Consequently, a least recently used data request is at the bottom of the stack. If a new request arrives when the stack is full, the least recently used request is removed from the bottom of the stack, and the new request is placed on the top of the stack.
The LRU caching algorithm is effective due to a characteristic of computer system operation called locality of reference. During any interval of time, data references are concentrated on a relatively small set of the elements assigned to the cache. Also, once a data element is referenced, the probability of it being re-referenced is highest soon after it is first referenced, with the probability of re-referencing diminishing as the time interval since the first reference increases.
A processor can access data from a cache in considerably less time than it can access data that is not in the cache. The satisfactory performance of the cache system depends, in part, on whether a desired item of data is in the cache at the time of re-referencing the data. Performance is therefore affected by the length of time for which the data is permitted to remain in the cache. When accessing data, if the data is in cache, the access is called a xe2x80x9ccache it.xe2x80x9d If the data is not in cache, the access is called a xe2x80x9ccache miss.xe2x80x9d
A single reference residency time (SRRT) of a storage subsystem cache is the length of time that passes between staging an item of data into the cache and aging it out, assuming that no reference to the data occurs after it is staged. The SRRT is an important indicator of cache performance. Generally, the longer the SRRT, i.e., the longer a unit of data remains in cache, the lesser the apparent demand on the cache. In contrast, a shorter SRRT indicates that the unit of data is overwritten sooner, and that the demand for cache resources is greater.
U.S. Pat. No. 5,452,440 to Salsburg, entitled xe2x80x9cMethod And Structure For Evaluating And Enhancing The Performance Of Cache Memory Systemsxe2x80x9d describes a method for determining which data should be placed into cache. However, the method does not determine the amount of time that the data remains in the cache.
U.S. Pat. No. 5,787,471 to Inoue et al., entitled xe2x80x9cCache Memory Management Apparatus Having A Replacement Method Based On The Total Data Retrieval Time And The Data Sizexe2x80x9d describes a cache memory management device. The device measures a time period required to obtain data from a database, and it also considers which data should be moved into the cache and which data should be removed from the cache. The device does not determine the amount of time that the data remains in the cache.
U.S. Pat. No. 5,606,688 to McNutt et al., entitled xe2x80x9cMethod And Apparatus For Dynamic Cache Memory Allocation Via Single-Reference Residency Timesxe2x80x9d, describes a method for managing a cache that includes measuring SRRT. However, the method requires access to an LRU list from the CCU. Consequently, this method can be used only in a system in which the CCU provides access to the LRU list.
U.S. Pat. No. 5,590,308 to Shih, entitled xe2x80x9cMethod And Apparatus For Reducing False Invalidations In Distributed Systemsxe2x80x9d describes a method for managing an LRU stack. The method considers a data residency time, but the time is determined by, and obtained from within, a CCU. Consequently, this method can be used only in a system in which the CCU is capable of reporting the data residency time.
Another approach to determining SRRT is offered by the Astex software product, available from Computer Associates, Inc. of Islandia, N.Y. Astex uses an input/output disconnect time to determine whether a data access is a cache hit or a cache miss, and thereafter estimates SRRT. A disconnect time of 0 corresponds to a cache hit, and a disconnect time of greater than 0 indicates a cache miss. The disconnect time cannot readily be obtained in all systems, so consequently, this method is limited to use with systems that report the disconnect time.
Accordingly, it is an object of the present invention to provide a method of determining the SRRT of a cache without requiring access to any information maintained within the CCU.
It is a second object of the present invention to provide a method for determining the SRRT of a cache that can be used generically, that is, independent of the platform upon which the method is employed.
In accordance with the invention, a method is provided for determining a single reference residency time of a cache. The method comprises the steps of causing test data to be staged to the cache and measuring a response time after a wait time has elapsed. The measuring step is repeated for a plurality of values of wait time. The method also includes the step of determining a boundary value of the wait time. A wait time of less than or equal to the boundary value yields a corresponding response time representing a cache hit and a wait time of greater than the boundary value yields a corresponding response time representing a cache miss. The boundary value is an estimate of the single reference residency time of the cache.